
(** 
    Commonly needed functions in day-to-day programming.
 *) 


(** {4 Exceptions} *)

exception Not_implemented
  (** Good for delaying work, or debugging by type checking *)

(* -------------------------------  Booleans  ------------------------------- *)

(** {4 [bool]} *) 

val xor : bool -> bool -> bool
  (** Exclusive \\/. *) 

(* -----------------------------  Combinators  ------------------------------ *)

(** {4 Combinators} *)

val ( ** ) : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b 
  (** Fuction composition. *) 

val ( % ) : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b 
  (** Alternative syntax for composition.  
      ( ** is occasionally overloaded.) *) 

val ( >> ) : ('a -> 'b) -> ('b -> 'c) -> 'a -> 'c 
  (** Reverse composition *) 

val ( |> ) : 'a -> ('a -> 'b) -> 'b 
  (** Function application. *) 

val apply : ('a -> 'b) -> 'a -> 'b
  (** Alternative syntax for application. *) 

val ( |-> ) : 'a * 'b -> ('a -> 'b -> 'c) -> 'c 
  (** Currying application. *) 

val ( |>> ) : 'a * 'b -> ('a -> 'c) -> 'c * 'b 
  (** Apply a function to the first element of a pair. *) 

val ( ||> ) : 'a * 'b -> ('b -> 'c) -> 'a * 'c 
  (** Apply a function to the second element of a pair. *) 

val ( ||>> ) : ('c * 'a) -> ('a -> 'd * 'b) -> ('c * 'd) * 'b
  (** Apply a function to the first element of a pair, with associativity. *) 

val curry : ('a * 'b -> 'c) -> 'a -> 'b -> 'c 
  (** Curry a function. *) 

val uncurry : ('a -> 'b -> 'c) -> 'a * 'b -> 'c 
  (** Uncurry a function. *) 

val i : 'a -> 'a 
  (** Identity. *) 

val id : 'a -> 'a 
  (** Alternate syntax for the identity. *) 

val k : 'a -> 'b -> 'a 
  (** K combinator. *)

val s : ('a -> 'b -> 'c) -> ('a -> 'b) -> 'a -> 'c 
  (** S combinator. *)

val c : ('a -> 'b -> 'c) -> 'b -> 'a -> 'c 
  (** Switch curried arguments. *) 

val w : ('a -> 'a -> 'b) -> 'a -> 'b
  (** Apply function twice to the same argument. *) 

(* ------------------------------  Functions  ------------------------------- *)

(** {4 Function Application} *)

val funpow : int -> ('a -> 'a) -> 'a -> 'a 
  (** Apply a function a given number of times. *) 

val repeat : ('a -> 'a) -> 'a -> 'a 
  (** Keep applying a function indefinitely. *) 

val eq : 'a -> 'a -> bool
  (** = *)

(* --------------------------------  Pairs  --------------------------------- *)

(** {4 Pairs} *)

val pair : 'a -> 'b -> 'a * 'b 
  (** Create a pair. *) 

val rpair : 'a -> 'b -> 'b * 'a 
  (** Create a pair, in reverse order. *) 

val swap : 'a * 'b -> 'b * 'a
  (** Swap the order of a pair. *) 

val apfst : ('a -> 'b) -> 'a * 'c -> 'b * 'c
val apsnd : ('b -> 'c) -> 'a * 'b -> 'a * 'c
val papply : ('a -> 'b) -> 'a * 'a -> 'b * 'b
val papply2 : ('a -> 'b) -> ('c -> 'd) -> 'a * 'c -> 'b * 'd

(* --------------------------------  Order  --------------------------------- *)

(** {4 Order} *)

type order = Less
             | Greater
             | Equal

val int_ord : int -> int -> order 
  (** Integer ordering. *) 
  
val string_ord : string -> string -> order 
  (** Lexicographic ordering on strings. *) 

(* -------------------------------  Failure  -------------------------------- *)

(** {4 Failure checking} *)

val can : ('a -> 'b) -> 'a -> bool 
val cant : ('a -> 'b) -> 'a -> bool 
val check : ('a -> bool) -> 'a -> 'a 

(* -------------------------------  Integers  ------------------------------- *)

(** {4 Integers} *)

val sum : int list -> int 
  (** Sum a list of numbers. *) 

val abs : int -> int 
  (** Absolute value. *) 

type sign = Positive | Negative

val sgn : int -> sign
  (** Sign of an int.  0 is considered positive. *) 

val gcd : int -> int -> int 
  (** Greatest common divisor. *)  

val lcm : int -> int -> int 
  (** Least common multiple. *)  

val odd : int -> bool 
  (** Odd. *)  

val even : int -> bool 
  (** Even. *)  

val ( ^^ ) : int -> int -> int 
  (** Power. *)  

val isqrt : int -> int * bool
  (** Integer square root.  Returns floor of the square root, and whether
      the result was exact. *)  

val posmod : int -> int -> int
  (** Return a positive remainder.  E.g., -1 mod 5 ~~> -1. posmod -1 5 ~~> 4. 
      Assumes the modulus is positive. *)

val posmod' : int -> int -> int
  (** Return a positive remainder.  E.g., -1 mod 5 ~~> -1. posmod -1 5 ~~> 4. 
      Modulus is unrestricted. *)

val ilog : int -> int -> int
  (** Integer logarithm. *) 

val fact : int -> int
  (** Factorial. *) 

val is_nan : float -> bool
val fabs : float -> float

(* -------------------------------------------------------------------------- *)
(*  Floats                                                                    *)
(* -------------------------------------------------------------------------- *)

val pi : float
val fabs : float -> float
val is_nan : float -> bool
val genlog : float -> float -> float

(* ------------------------------------------------------------------------- *)
(*  Debug								     *)
(* ------------------------------------------------------------------------- *)

val report : string -> unit 
val warn : bool -> string -> unit 
val verbose : bool ref 
val report_timing : bool ref
val remark : string -> unit 
val time : ('a -> 'b) -> 'a -> 'b 
val get_time : ('a -> 'b) -> 'a -> 'b * float 

(* ------------------------------------------------------------------------- *)
(*  Refs								     *)
(* ------------------------------------------------------------------------- *)

val ( += ) : int ref -> int -> unit 
val ( -= ) : int ref -> int -> unit 
val ( *= ) : int ref -> int -> unit 
val ( /= ) : int ref -> int -> unit 
val ( +.= ) : float ref -> float -> unit 
val ( +:= ) : 'a list ref -> 'a -> unit 
val ( -:= ) : 'a list ref -> 'a -> unit 
val ( @= ) : 'a list ref -> 'a list -> unit 
val skip : 'a -> unit

(* ------------------------------------------------------------------------- *)
(*  Triples								     *)
(* ------------------------------------------------------------------------- *)

val fst3 : 'a * 'b * 'c -> 'a 
val snd3 : 'a * 'b * 'c -> 'b 
val thd3 : 'a * 'b * 'c -> 'c 
val zip3 : 'a list -> 'b list -> 'c list -> ('a * 'b * 'c) list
val unzip3 : ('a * 'b * 'c) list -> 'a list * 'b list * 'c list

(* ------------------------------------------------------------------------- *)
(*  Lists								     *)
(* ------------------------------------------------------------------------- *)

(* These are list library functions, some with modified names *)
val length : 'a list -> int 
  (** raises Failure *)
val hd : 'a list -> 'a 
  (** raises Failure *)
val tl : 'a list -> 'a list 
  (** raises Failure *)
val nth : 'a list -> int -> 'a 
  (** nth element of a list, @raises Failure *)
val rev : 'a list -> 'a list 
val append : 'a list -> 'a list -> 'a list
val rev_append : 'a list -> 'a list -> 'a list
val flatten : 'a list list -> 'a list 
val iter : ('a -> unit) -> 'a list -> unit 
val map : ('a -> 'b) -> 'a list -> 'b list 
val rev_map : ('a -> 'b) -> 'a list -> 'b list 
  (** fold_left f x l = f (f (f x l1) l2) l3 ... *) 
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
val foldl : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
val fold_left_end : ('a -> 'a -> 'a) -> 'a list -> 'a
val foldl_end : ('a -> 'a -> 'a) -> 'a list -> 'a
  (** fold_right f l x = f l1 (f l2 (f l3 x)) ... *) 
val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b
val foldr : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b
val fold_right_end : ('a -> 'a -> 'a) -> 'a list -> 'a
val foldr_end : ('a -> 'a -> 'a) -> 'a list -> 'a
  (* raises Invalid_argument *)
val iter2 : ('a -> 'b -> unit) -> 'a list -> 'b list -> unit 
  (* raises Invalid_argument *)
val map2 : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list 
  (* raises Invalid_argument *)
val rev_map2 : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list 
  (* raises Invalid_argument *)
val fold_left2 : ('a -> 'b -> 'c -> 'a) -> 'a -> 'b list -> 'c list -> 'a
  (* raises Invalid_argument *)
val fold_right2 : ('a -> 'b -> 'c -> 'c) -> 'a list -> 'b list -> 'c -> 'c
val forall : ('a -> bool) -> 'a list -> bool 
val exists : ('a -> bool) -> 'a list -> bool 
  (* raises Invalid_argument *)
val forall2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool 
  (* raises Invalid_argument *)
val exists2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool 
val mem : 'a -> 'a list -> bool 
val memq : 'a -> 'a list -> bool 
val insert : 'a -> 'a list -> 'a list
  (* all elements of l1 not occuring in l2 *)
val diff : 'a list -> 'a list -> 'a list 
  (* raises Not_found *)
val find : ('a -> bool) -> 'a list -> 'a 
val filter : ('a -> bool) -> 'a list -> 'a list 
val partition : ('a -> bool) -> 'a list -> 'a list * 'a list 
  (* raises Not_found *)
val assoc : 'a -> ('a * 'b) list -> 'b  
val try_assoc : 'a -> ('a * 'b) list -> string -> 'b  
  (* raises Not_found *)
val assq : 'a -> ('a * 'b) list -> 'b 
val mem_assoc : 'a -> ('a * 'b) list -> bool 
val mem_assq : 'a -> ('a * 'b) list -> bool
val remove_assoc : 'a -> ('a * 'b) list -> ('a * 'b) list
val remove_assq : 'a -> ('a * 'b) list -> ('a * 'b) list
  (* raises Invalid_argument *)
val zip : 'a list -> 'b list -> ('a * 'b) list 
val unzip : ('a * 'b) list -> 'a list * 'b list 
val gen_sort : ('a -> 'a -> int) -> 'a list -> 'a list 
val sort : 'a list -> 'a list 
val stable_sort : ('a -> 'a -> int) -> 'a list -> 'a list 
val fast_sort : ('a -> 'a -> int) -> 'a list -> 'a list 
val gen_index : ('a -> bool) -> 'a list -> int
val index : 'a -> 'a list -> int

(* Extras *)
val null : 'a list -> bool 
val cons : 'a -> 'a list -> 'a list 
val list : 'a -> 'a list 
val mapi : (int -> 'a -> 'b) -> 'a list -> 'b list 
  (* raises Failure *)
val last : 'a list -> 'a 
  (* raises Failure *)
val butlast : 'a list -> 'a list 
  (* raises Failure *)
val gen_max : ('a -> 'a -> bool) -> 'a list -> 'a 
val maxl : 'a list -> 'a 
  (* raises Failure *)
val gen_min : ('a -> 'a -> bool) -> 'a list -> 'a 
val minl : 'a list -> 'a 

(* other iterators *)
(** itlist f xs y = f x1 (...(f xn-1 (f xn y))) *) 
(** itlist = fold_right *) 
val itlist : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b 
  (** rev_itlist f l x = f l_n (f l_{n-1} (...(f l_1 (f l_0 x))...))  *)
val rev_itlist : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b 
val end_itlist : ('a -> 'a -> 'a) -> 'a list -> 'a 
val rev_end_itlist : ('a -> 'a -> 'a) -> 'a list -> 'a 

val itlist2 : ('a -> 'b -> 'c -> 'c) -> 'a list -> 'b list -> 'c -> 'c 
val rev_itlist2 : ('a -> 'b -> 'c -> 'c) -> 'a list -> 'b list -> 'c -> 'c
  (* iterate using element position in list *)
val nitlist : (int -> 'a -> 'b -> 'b) -> 'a list -> 'b -> 'b 
val niter : (int -> 'a -> unit) -> 'a list -> unit
val rev_nitlist : (int -> 'a -> 'b -> 'b) -> 'a list -> 'b -> 'b 

(* uncurried fold_left *)
val pfold_left : ('a * 'b -> 'a) -> 'a * 'b list -> 'a 
  (* uncurried fold_right *)
val pfold_right : ('a * 'b -> 'b) -> 'a list * 'b -> 'b 
  (* fold_left and map simultaneously *)
val foldl_map : ('a * 'b -> 'a * 'c) -> 'a * 'b list -> 'a * 'c list 
  (* itlist, using last element as base *)

val replicate : 'a -> int -> 'a list 
val upto : int -> int -> int list 
val ( -- ) : int -> int -> int list 
val ( --< ) : int -> int -> int list 
val uptoby : int -> int -> int -> int list

val filter_out : ('a -> bool) -> 'a list -> 'a list 
  (** opposite of filter *)

val tryfind : ('a -> 'b) -> 'a list -> 'b 
  (** raises Failure *)

(** raises Failure *)
val delete : 'a -> 'a list -> 'a list 
val delete_all : 'a -> 'a list -> 'a list 

val rem : 'a -> 'a list -> 'a list 
  (** raises Not_found *)

val rem' : 'a -> 'a list -> 'a list 
  (** no exceptions *)

val chop_list : int -> 'a list -> 'a list * 'a list 

val split_list : int -> 'a list -> 'a list list

val chop_head : ('a -> bool) -> 'a list -> 'a list
  (** cut the elements off the head of a list that satisfy a predicate
      e.g., eliminate the first zeros in a list of bits for normalization *)

val take : int -> 'a list -> 'a list
val drop : int -> 'a list -> 'a list
val indices : 'a -> 'a list -> int list 
val shuffle : 'a list -> 'a list -> 'a list 
val rev_assoc : 'a -> ('b * 'a) list -> 'b  
val allpairs : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list 
val allcombs : ('a -> 'a -> 'b) -> 'a list -> 'b list 
val product : 'a list -> 'b list -> ('a * 'b) list 
val mappair : ('a -> 'b) -> ('c -> 'd) -> ('a * 'c) list -> ('b * 'd) list 
val add : 'a -> 'a list -> 'a list
  (** cons an element to a list if it's not already a member *)
val insertat : int -> 'a -> 'a list -> 'a list 
  (** insert an element at a specific position *)
val rev_nth : int -> 'a list -> 'a 
  (*
    swap_lists [[1;2;3];[4;5;6];[7;8;9];[10;11;12]] --> 
    [[1; 4; 7; 10]; [2; 5; 8; 11]; [3; 6; 9; 12]]
   *)
val swap_lists : 'a list list -> 'a list list 
val gen_mem : ('a -> 'b -> bool) -> 'a -> 'b list -> bool
val gen_rem : ('a -> 'b -> bool) -> 'a -> 'b list -> 'b list
val cycle : 'a list -> 'a list
val rotate : 'a list -> int -> 'a list
  (** splits a list at the given element, which is discarded *)
val split_at : 'a -> 'a list -> 'a list * 'a list
  (** update l n a changes the element at position n of l to a *)
val update : 'a list -> int -> 'a -> 'a list
  (** map_at ns f l applies f to the elements indexed by ns in l *)
val map_at : int list -> ('a -> 'a) -> 'a list -> 'a list
  (** replace x ys zs replaces the first x in zs with ys *)
val replace : 'a -> 'a list -> 'a list -> 'a list

val setify : 'a list -> 'a list
val union : 'a list -> 'a list -> 'a list
val intersect : 'a list -> 'a list -> 'a list
val subtract : 'a list -> 'a list -> 'a list
val subset : 'a list -> 'a list -> bool
val psubset : 'a list -> 'a list -> bool
val set_eq : 'a list -> 'a list -> bool
val insert : 'a -> 'a list -> 'a list
val smap : ('a -> 'b) -> 'a list -> 'b list
val unions : 'a list list -> 'a list
val allsets : int -> 'a list -> 'a list list
val allsubsets : 'a list -> 'a list list
val allnonemptysubsets : 'a list -> 'a list list
val distinctpairs : 'a list -> ('a * 'a) list
val non : ('a -> bool) -> 'a  -> bool
val permutations : 'a list -> 'a list list
val combinations : 'a list list -> 'a list list

(* ------------------------------------------------------------------------- *)
(*  Options								     *)
(* ------------------------------------------------------------------------- *)

val is_some : 'a option -> bool 
val is_none : 'a option -> bool 
val the : 'a option -> 'a 
  (** Extract from an option. *)
val get_opt : 'a option -> string -> 'a 
val try_app : ('a -> 'b) -> 'a -> 'b option
  (** Extract from an option.  Second argument is an error message. *)
val gen_opt : 'a option -> 'a -> 'a 
val find' : ('a -> bool) -> 'a list -> 'a option
val assoc' : 'a-> ('a * 'b) list -> 'b option
val rev_assoc' : 'a-> ('b * 'a) list -> 'b option
val map_partial : ('a -> 'b option) -> 'a list -> 'b list 
  (** keep all elements that evaluate to Some *)
val gen_index' : ('a -> bool) -> 'a list -> int option 
val index' : 'a -> 'a list -> int option 
val apply' : ('a -> 'b) -> 'a option -> 'b option
val find_opt : ('a -> 'b option) -> 'a list -> 'b option

(* -------------------------------------------------------------------------- *)
(*  Lazy evaluation                                                           *)
(* -------------------------------------------------------------------------- *)

type ('a,'b)lazysum = Unrealized of (('a ->'b) * 'a) | Realized of ('b);;
val lazify : ('a -> 'b) -> 'a -> ('a,'b) lazysum ref
val eager : 'b -> ('a,'b) lazysum ref
val eval : ('a,'b) lazysum ref -> 'b

(* ------------------------------------------------------------------------- *)
(*  Arrays								       *)
(* ------------------------------------------------------------------------- *)

module Array' :
sig
  (* array funs *)
  val length : 'a array -> int
  val get : 'a array -> int -> 'a
  val set : 'a array -> int -> 'a -> unit 
  val make : int -> 'a -> 'a array
  val create : int -> 'a -> 'a array
  val init : int -> (int -> 'a) -> 'a array
  val make_matrix : int -> int -> 'a -> 'a array array
  val create_matrix : int -> int -> 'a -> 'a array array
  val append : 'a array -> 'a array -> 'a array
  val concat : 'a array list -> 'a array
  val sub : 'a array -> int -> int -> 'a array
  val copy : 'a array -> 'a array
  val fill : 'a array -> int -> int -> 'a -> unit
  val blit : 'a array -> int -> 'a array -> int -> int -> unit
  val to_list : 'a array -> 'a list
  val of_list : 'a list -> 'a array
  val iter : ('a -> unit) -> 'a array -> unit
  val map : ('a -> 'b) -> 'a array -> 'b array
  val iteri : (int -> 'a -> unit) -> 'a array -> unit
  val mapi : (int -> 'a -> 'b) -> 'a array -> 'b array
  val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b array -> 'a
  val fold_right : ('a -> 'b -> 'b) -> 'a array -> 'b -> 'b
  val sort : ('a -> 'a -> int) -> 'a array -> unit
  val stable_sort : ('a -> 'a -> int) -> 'a array -> unit
  val fast_sort : ('a -> 'a -> int) -> 'a array -> unit
  val unsafe_get : 'a array -> int -> 'a
  val unsafe_set : 'a array -> int -> 'a -> unit
    (* extensions *)
  val foldl : ('a -> 'b -> 'a) -> 'a -> 'b array -> 'a
  val foldr : ('a -> 'b -> 'b) -> 'a array -> 'b -> 'b
  val foldl_end : ('a -> 'a -> 'a) -> 'a array -> 'a
  val foldr_end : ('a -> 'a -> 'a) -> 'a array -> 'a
  val find : ('a -> bool) -> 'a array -> 'a option
  val index : 'a -> 'a array -> int option
  val indices : 'a -> 'a array -> int list
  val exists : ('a -> bool) -> 'a array -> bool
  val exists2 : ('a -> 'b -> bool) -> 'a array -> 'b array -> bool
  val forall : ('a -> bool) -> 'a array -> bool
  val forall2 : ('a -> 'b -> bool) -> 'a array -> 'b array -> bool
  val blit' : source:'a array -> dest:'a array -> unit
  val min : 'a array -> 'a
  val gen_min : ('a -> 'a -> bool) -> 'a array -> 'a
  val max : 'a array -> 'a
  val gen_max : ('a -> 'a -> bool) -> 'a array -> 'a
  val map2 : ('a -> 'b -> 'c) -> 'a array -> 'b array -> 'c array
  val map2i : (int -> 'a -> 'b -> 'c) -> 'a array -> 'b array -> 'c array
  val itlist2 : ('a -> 'b -> 'c -> 'c) -> 'a array -> 'b array -> 'c -> 'c
  val swap : 'a array -> int -> int -> unit
  val zip : 'a array -> 'b array -> ('a * 'b) array
  val unzip : ('a * 'b) array -> 'a array * 'b array
  val transpose : 'a array array -> 'a array array
end

(* -------------------------------------------------------------------------- *)
(*  Stack                                                                     *)
(* -------------------------------------------------------------------------- *)

module Stack' :
sig
  val to_list : 'a Stack.t -> 'a list
  val to_string : ('a -> string) -> 'a Stack.t -> string
  val print : ('a -> unit) -> 'a Stack.t -> unit
end  

(* -------------------------------------------------------------------------- *)
(*  Sets                                                                      *)
(* -------------------------------------------------------------------------- *)

module Set' :
sig
  module type OrderedType = Set.OrderedType
  module type S =
  sig
    include Set.S
    val forall : (elt -> bool) -> t -> bool
    val insert : elt -> t -> t
    val insert_many : elt list -> t -> t
    val pop : t -> elt * t
    val pop' : t -> (elt * t) option
    val of_list : elt list -> t
    val to_list : t -> elt list
    module Ops :
    sig
      val ( *= ) : t ref -> t -> unit
      val ( += ) : t ref -> t -> unit
      val ( -= ) : t ref -> t -> unit
      val ( %= ) : t ref -> elt -> unit
    end
  end
  module Make(Ord : OrderedType) : S with type elt = Ord.t
end

module IntSet : Set'.S
module StringSet : Set'.S

(* -------------------------------------------------------------------------- *)
(*  Queues                                                                    *)
(* -------------------------------------------------------------------------- *)

module Queue' :
sig 
  val mem : 'a Queue.t -> 'a -> bool
  val add_unique : 'a -> 'a Queue.t -> unit
  val to_list : 'a Queue.t -> 'a list
  val to_string : ('a -> string) -> 'a Queue.t -> string
  val print : ('a -> unit) -> 'a Queue.t -> unit
end

(* -------------------------------------------------------------------------- *)
(*  Hashtables                                                                *)
(* -------------------------------------------------------------------------- *)

module Hashtbl' :
sig 
  (* library *)
  type ('a, 'b) t 
  val create : int -> ('a, 'b) t
  val clear : ('a, 'b) t -> unit
  val add : ('a, 'b) t -> 'a -> 'b -> unit
  val copy : ('a, 'b) t -> ('a, 'b) t
  val find : ('a, 'b) t -> 'a -> 'b
  val find_all : ('a, 'b) t -> 'a -> 'b list
  val mem : ('a, 'b) t -> 'a -> bool
  val remove : ('a, 'b) t -> 'a -> unit
  val replace : ('a, 'b) t -> 'a -> 'b -> unit
  val iter : ('a -> 'b -> unit) -> ('a, 'b) t -> unit
  val fold : ('a -> 'b -> 'c -> 'c) -> ('a, 'b) t -> 'c -> 'c
  val length : ('a, 'b) t -> int
  module type HashedType =
  sig type t val equal : t -> t -> bool val hash : t -> int end
  module type S =
  sig
    type key
    type 'a t
    val create : int -> 'a t
    val clear : 'a t -> unit
    val copy : 'a t -> 'a t
    val add : 'a t -> key -> 'a -> unit
    val remove : 'a t -> key -> unit
    val find : 'a t -> key -> 'a
    val find_all : 'a t -> key -> 'a list
    val replace : 'a t -> key -> 'a -> unit
    val mem : 'a t -> key -> bool
    val iter : (key -> 'a -> unit) -> 'a t -> unit
    val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
    val length : 'a t -> int
  end
  module Make :
    functor (H : HashedType) ->
  sig
    type key = H.t
    type 'a t = 'a Hashtbl.Make(H).t
    val create : int -> 'a t
    val clear : 'a t -> unit
    val copy : 'a t -> 'a t
    val add : 'a t -> key -> 'a -> unit
    val remove : 'a t -> key -> unit
    val find : 'a t -> key -> 'a
    val find_all : 'a t -> key -> 'a list
    val replace : 'a t -> key -> 'a -> unit
    val mem : 'a t -> key -> bool
    val iter : (key -> 'a -> unit) -> 'a t -> unit
    val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
    val length : 'a t -> int
  end
  val hash : 'a -> int
  val hash_param : int -> int -> 'a -> int
    (* extensions *)  
  val find' : ('a,'b) t -> 'a -> 'b option
  val unique_add : ('a,'b) t -> 'a -> 'b -> unit 
    (** fails if key is present *)
  val to_list : ('a,'b) t -> ('a * 'b) list
  val to_string : ('a * 'b -> string) -> ('a,'b) t -> string
  val print : ('a * 'b -> unit) -> ('a,'b) t -> unit
end

(* -------------------------------------------------------------------------- *)
(*  Chars                                                                     *)
(* -------------------------------------------------------------------------- *)

val char_to_string : char -> string
val is_upper : char -> bool
val is_lower : char -> bool
val is_numeral : char -> bool

(* -------------------------------------------------------------------------*)
(*  Strings				                 		    *)
(* -------------------------------------------------------------------------*)

val concat : string list -> string 
val implode : string list -> string 
val explode : string -> string list 
val paren : string -> string
val quote : string -> string
val bracket : string -> string
val curly : string -> string
val abracket : string -> string
val separate : string -> string list -> string
val commas : string list -> string
val semis : string list -> string
val scommas : string list -> string
val ssemis : string list -> string
val spaces : string list -> string
val n_spaces : int -> string
val string_of_list : ('a -> string) -> 'a list -> string
val string_of_array : ('a -> string) -> 'a array -> string
val string_of_pair : ('a -> string) -> ('b -> string) -> 'a * 'b -> string
val string_of_option : ('a -> string) -> 'a option -> string
val string_of_char_list : char list -> string
val split_string : char -> string -> string list
val capitalize : string -> string
val lowercase : string -> string


(* -------------------------------------------------------------------------- *)
(*  Misc signatures                                                           *)
(* -------------------------------------------------------------------------- *)

module type NONEMPTY =
sig
  type t
  val default : t
end  

module type SIZE =
sig
  val size : int
end

module type KEY =
sig
  type key
  val ord : key -> key -> order
  val to_string : key -> string
end

module IntKey : KEY with type key = int
module StringKey : KEY with type key = string

(* ------------------------------------------------------------------------- *)
(*  Printing                                                                 *)
(* ------------------------------------------------------------------------- *)

val print_stringl : string -> unit
val print_box_string : string -> unit
val gen_print_list : (int -> 'a -> unit) -> (int -> unit) -> 'a list -> unit
val print_list : ('a -> unit) -> 'a list -> unit
val print_list_nl : ('a -> unit) -> 'a list -> unit
val print_int_list : int list -> unit
val print_pair : ('a -> unit) -> ('b -> unit) -> 'a * 'b -> unit
val print_ref : ('a -> unit) -> 'a ref -> unit
val print_option : ('a -> unit) -> 'a option -> unit
val float_precision : int ref
val float_to_string : float -> string
val print_float : float -> unit
val newlines : int -> string

(* -------------------------------------------------------------------------- *)
(*  IO                                                                        *)
(* -------------------------------------------------------------------------- *)

val write_file : string -> string -> unit
  (** write_file fname contents *)

val read_file : string -> string
  (** read the whole file into a string *)

val output_stringl : out_channel -> string -> unit
  (** write a string with a newline appended. *)
